package datastruct

//多用于解决前缀问题
type TrieTree struct {
	root *TrieNode
}

type TrieNode struct {
	value        string
	children     [26]*TrieNode
	isEndingChar bool
}

func (t *TrieTree) Insert(s string) {
	if t.root == nil {
		t.root = &TrieNode{
			value:        "/",
			children:     [26]*TrieNode{},
			isEndingChar: false,
		}
	}
	p := t.root
	for i := 0; i < len(s); i++ {
		index := int(s[i] - 'a')
		if p.children[index] == nil {
			p.children[index] = &TrieNode{
				value:        string(s[i]),
				children:     [26]*TrieNode{},
				isEndingChar: false,
			}
		}
		p = p.children[index]
	}
	p.isEndingChar = true
}

func (t *TrieTree) Search(s string) bool {
	if t.root == nil {
		return false
	}
	p := t.root
	for i := 0; i < len(s); i++ {
		index := int(s[i] - 'a')
		if p.children[index] == nil {
			return false
		}
		p = p.children[index]
	}
	if p.isEndingChar{
		return true
	}
	return false
}

func (t *TrieTree) StartsWith(s string) bool {
	if t.root == nil {
		return false
	}
	p := t.root
	for i := 0; i < len(s); i++ {
		index := int(s[i] - 'a')
		if p.children[index] == nil {
			return false
		}
		p = p.children[index]
	}
	return true
}